//
//  Problem1578.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1578. 避免重复字母的最小删除成本
 给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。
 返回使字符串任意相邻两个字母不相同的最小删除成本。
 请注意，删除一个字符后，删除其他字符的成本不会改变。


 示例 1：
     输入：s = "abaac", cost = [1,2,3,4,5]
     输出：3
     解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。
 示例 2：
     输入：s = "abc", cost = [1,2,3]
     输出：0
     解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。
 示例 3：
     输入：s = "aabaa", cost = [1,2,3,4,1]
     输出：2
    解释：删除第一个和最后一个字母，得到字符串 ("aba") 。

 提示：
     s.length == cost.length
     1 <= s.length, cost.length <= 10^5
     1 <= cost[i] <= 10^4
     s 中只含有小写英文字母
 */
@objcMembers class Problem1578: NSObject {
    func solution() {
        print(minCost("abaac", [1,2,3,4,5]))
        print(minCost("abc", [1,2,3]))
        print(minCost("aabaa", [1,2,3,4,1]))
    }
    
    /*
     1: 创建一个字符lastC，记录第一个字符
     2: 从1开始遍历字符串，遇到和lastC相同的，就相加sum += cost[i], 同时统计最大的cost[i]
     3: 遇到与lastC不相同的字符，那么计算sum - 最大的cost[i] (最小删除成本), 让lastC = 当前字符，继续遍历
     */
    func minCost(_ s: String, _ cost: [Int]) -> Int {
        if s.count <= 1 {
            return 0
        }
        let charts = Array(s)
        var lastC: Character = charts[0]
        var sum = cost[0]
        var maxvalue = sum
        for i in 1..<charts.count {
            if charts[i] == lastC {
                sum += cost[i]
                maxvalue = max(maxvalue, cost[i])
            } else {
                sum -= maxvalue - cost[i]
                maxvalue = cost[i]
                lastC = charts[i]
            }
        }
        
        return sum - maxvalue
    }
}
